1. Field of the Invention
This invention relates to high speed arithmetic units. More specifically, the apparatus relates to logical hardware arranged to perform a division operation.
2. Description of the Prior Art
Most small electronic computing machines and central processing units presently employ arithmetic units capable of performing division. Even hand held calculators are capable of performing division operations. The simplest form of binary division is performed as a reverse procedure of multiplication. The quotient in binary division is calculated through successive substraction of the divisor from appropriate orders of the dividend. Each time the substraction operation leaves a positive remainder, a binary one is added to the corresponding order of the quotient. Each time a negative remainder would result, a binary zero is added to the corresponding order of the quotient and steps must be taken which will, in effect, nullify the substraction and leave the quotient unchanged. The problem created by the handling of the negative remainder has been treated in several ways, all of which are time consuming and have heretofore created a requirement for extensive complex logic. Recent developments in large scale integrated circuitry have enabled the manufacture of such logic circuits at extremely low cost; however, the use of such logic has increased the time required to produce a quotient.
Several techniques for handling the negative remainder are known, such as adding the divisor back to the remainder each time a negative remainder occurs. Another method for producing the quotient when the remainder becomes negative as a result of substracting the divisor is to shift the divisor to the right and add it to the negative remainder. When the divisor is shifted to the right one bit, it is effectively divided by two. If the remainder changes from negative to positive, the partial quotient bit is a binary one. Each time the divisor is subtracted from the positive remainder and it becomes negative, the partial quotient is a binary zero.
Also, look ahead methods have been suggested, wherein, the divisor is compared with appropriate orders of the dividend (or the remainder) so that subtraction of the divisor will always produce a positive remainder.
All of the aforementioned division methods require software or logic hardware, which executes a decision making function.
Carroll et al., U.S. Pat. No. 3,064,896 for an Asynchronous Division Apparatus, teaches an apparatus capable of performing division operations in a data processing machine at high speeds. The apparatus of this patent employs the principles of nonrestoring binary division, wherein, the quotient is obtained through successive subtractions of the divisor from appropriate orders of the dividend using adder circuitry. When the divisor is positive, it is converted to one's complement form before being added to the positive dividend. Now the number in the divisor register is negative as a result of having been complemented and it must be converted to a two complement form before being added to the positive dividend to assure that the data portion of the number, resulting from the subtraction, is correct whether or not there is an end carry of a one bit into the sign position.
After this double manipulation of the divisor in a high speed serial adder, the number in the divisor register may be added to the dividend number to effect a subtraction iteration. When there is a carry out of a one bit from the sign stage of the accumulator, the difference is positive and a one bit is stored in the least significant digit stage of the quotient register indicative of the most significant bit of the quotient. When the remainder stored in the accumulator is negative, as indicated by a zero in the sign stage, the divisor in the divisor register does not require complementing and these two unaltered values may be added to effect the next subtraction iteration. However, the zero in the sign bit of the accumulator is indicative of a zero quotient bit.
Numerous applications exist where it is desirable to provide for high speed division computations. Heretofore, such apparatus has only been found in high speed data processing machines having complex circuitry. As an example, the accuracy of an antenna position is a function of the smallest increment which may be detected while it is moving. The increment of movement can only be made smaller when the angular positions of rotation are made extremely fast. The calculation of the increment of rotation is made by a division computation, thus, it would be desirable to provide a simple, economical high speed dividing apparatus without the need for software implementation.
Heretofore, high speed apparatus for performing division operations has been complex and as a result, has required more operations than usually performed in a simple binary multiplication operation involving repetitive binary addition.